Bingo, Computer Graphics & Game Developer

Monte Carlo Integration

蒙特卡洛方法求积分以及部分所需的概率论术语可以在PBRT以及概率论与数理统计中找到

PBRT中给出了蒙特卡洛估计量,其中随机变量Xi[a,b]X_i \in [a,b]且独立同分布,分布满足概率密度函数 p(x)p(x)

FN=1Ni=1Nf(Xi)p(Xi)F_N = \frac{1}{N}\sum^{N}_{i=1}\frac{f(X_i)}{p(X_i)}

其期望为

E[FN]=E[1Ni=1Nf(Xi)p(Xi)]=1Ni=1Nabf(x)p(x)p(x)dx=1Ni=1Nabf(x)dx=abf(x)dx\begin{array}{l}
E[F_N] & = E[\frac{1}{N}\sum_{i=1}^{N}\frac{f(X_i)}{p(X_i)}] \\
& = \frac{1}{N}\sum_{i=1}^{N}\int_{a}^{b}\frac{f(x)}{p(x)}p(x)dx \\
& = \frac{1}{N}\sum_{i=1}^{N}\int_{a}^{b}f(x)dx \\
& = \int_{a}^{b}f(x)dx \\
\end{array}

方差为

σ2=1N(f(x)p(x)I)2p(x)dx\sigma^2=\frac{1}{N}\int(\frac{f(x)}{p(x)}-I)^2p(x)dx

结果的误差与标准差成正比,因此随着样本数增加误差缩小速度仅与N\sqrt{N}相关(即常说的增加4倍采样数目才能缩小一半的误差)

PBRT以及许多其他文章书籍等直接给出了这个估计量的期望计算(其中第二步到第三步并未直接说明来由,尽管PBRT在对期望的简介中已给出式子),这一步只能证明估计量本身无偏*

以下将给出证明

引用一个知识点: Law of the unconscious statistician,简称LOTUS。用法是已知随机变量X的分布fXf_X,但并不知道函数g(X)的分布fg(X)f_{g(X)}。那么此时函数g(X)g(X)的期望为

E[g(X)]=xg(x)fX(x)E[g(X)]=\sum_x g(x)f_X(x)(X为离散型随机变量)

E[g(X)]=g(x)fX(x)dxE[g(X)]=\int_{-\infty}^{\infty} g(x)f_X(x)dx(X为连续型随机变量)

此处细节介绍也可以看Wyman的技术博客,其中就提到了许多地方都没有涉及到的LOTUS。

E[f(Xi)pdf(Xi)]=E[f(x)pdf(x)]=abf(x)pdf(x)pdf(x)dx=abf(x)dx\begin{array}{l}
E[ \frac {f(X_{i})}{pdf(X_{i})} ] & = E[ \frac {f(x)}{pdf(x)} ] \\
& = \int _{a}^{b}\frac {f(x)}{pdf(x)}pdf(x)dx \\
& = \int _{a}^{b}f(x)dx
\end{array}

这里积分区间变为[,][-\infty, \infty]也是如此。以下将会使用到大数定律的知识背景。

引用自维基百科:设 a1,a2,...,an,...a_{1},a_{2},…,a_{n},…为相互独立的随机变量,其数学期望为: E(ai)=μ(i=1,2,...)E(a_{i})=\mu (i=1,2,…),方差为: Var(ai)=σ2(i=1,2,...)Var(a_{i})=\sigma ^{2}(i=1,2,…)
则序列a=1ni=1n\overline{a} = \frac{1}{n} \sum_{i=1}^{n}aia_{i} 依概率收敛于 μ\mu(即收敛于此数列的数学期望 E(ai)E(a_{i}))。

取一组独立同分布的随机变量{ξ}\{\xi\},且ξ\xi[a,b][a,b]内满足分布律p(x)p(x),则令p(x)=f(x)p(x)p^(x)=\frac{f(x)}{p(x)},**则{p(ξi)}\{ p^(\xi_i) \}也是一组独立同分布的随机变量。**,那么计算其得到的期望其实就是积分本身(见下)。

由大数定理

Pr(limN1Ni=1Np(ξi)=I)=1Pr(\lim_{N\to\infty}\frac{1}{N}\sum_{i=1}^{N}p^*(\xi_i)=I)=1

那么这里已经有随机变量{p(ξi)}\{ p^(\xi_i) \}存在,且期望等于积分值,**那么根据大数定理可知,这里的{p(ξi)}\{ p^(\xi_i) \}就是会依概率收敛于积分值。**证毕。